package com.linzm.leetcode.primary.数组.二分法;


/**
 * @Author zimingl
 * @Date 2022/10/6 14:08
 * @Description: TODO
 */
public class 数组34在排序数组中查找元素的第一个和最后一个位置 {

    /**
     * 寻找target在数组里的左右边界，有如下三种情况：
     * 情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
     * 情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
     * 情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}
     * 这三种情况都考虑到，说明就想的很清楚了。
     * 接下来，在去寻找左边界，和右边界了。
     * 采用二分法来去寻找左右边界，为了让代码清晰，我分别写两个二分来寻找左边界和右边界。
     */
    private static int getRightBorder(int[] nums, int target){
        int left = 0;
        int right = nums.length - 1;
        int rightBorder = -2;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (target >= nums[mid]){
                left = mid + 1;
                rightBorder = left;
            } else {
                right = mid - 1;
            }
        }
        return  rightBorder;
    }

    private static int getLeftBorder(int[] nums, int target){
        int left = 0;
        int right = nums.length - 1;
        int leftBorder = -2;
        while (left <= right){
            int mid = left + (right - left)/2;
            if (target <= nums[mid]){
                right = mid - 1;
                leftBorder = right;
            } else {
                left = mid + 1;
            }
        }
        return  leftBorder;
    }

    private static int[] searchRange(int[] nums, int target){
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一
        if (leftBorder == -2 || rightBorder == -2)
            return new int[]{-1, -1};
        // 情况三
        if (rightBorder - leftBorder > 1)
            return new int[]{leftBorder + 1, rightBorder - 1};
        // 情况二
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int[] nums = new int[]{5,7,7,8,8,8,10};
        int target = 12;
        int[] ints = searchRange(nums, target);
        for (int i: ints) {
            System.out.printf(i + "\t");
        }
    }
}
